package com.zsj.queue;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/3/29 19:08
 * @Description 小顶堆
 */
public class MinHeap {
    ListNode[] array;
    int size;
    public MinHeap(int capacity) {
        array = new ListNode[capacity];
    }
    public boolean offer(ListNode value) {
        if (isFull()) return false;
        //添加元素
        int child = size++;
        int parent = (child - 1) / 2;
        //向上交换 当前需要添加节点的值小于父节点的值
        while (child > 0 && value.val < array[parent].val) {
            //交换
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = value;
        return true;
    }
    public ListNode poll() {
        if (isEmpty()) return null;
        swap(0, size - 1);
        size--;
        ListNode priority = array[size];
        array[size] = null;//help gc
        down(0);
        return priority;
    }
    private void down(int parent) {
        int left = 2 * parent + 1;
        int right = left + 1;
        int min = parent;
        if (left < size && array[left].val < array[min].val) {
            //如果左边小于了当前父节点的优先级
            min = left;
        }
        if (right < size && array[right].val < array[min].val) {
            min = right;
        }
        if (min != parent) {
            swap(min, parent);
            down(min);
        }
    }
    private void swap(int src, int end) {
        ListNode temp = array[src];
        array[src] = array[end];
        array[end] = temp;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public boolean isFull() {
        return size == array.length;
    }
}
